package in.hitmedia.test.trees;

import java.util.Arrays;

public class Heap 
{

	private int size = 0;
	
	private Integer a[] = new Integer[1024];
	
	
	public void incrementSize()
	{
		size++;
	}
	
	public void decrementSize()
	{
		size--;
	}
	
	public int left(int i)
	{
		return 2*i+1;
	}
	
	public int right(int i)
	{
		return 2*(i+1);
	}
	
	public int parent(int i)
	{
		return (i-1)/2;
	}
	
	public Integer min()
	{
		if (size > 0)
		{
			Integer ret = a[0];
			a[0] = a[size-1];
			decrementSize();
			heapify(0);
			return ret;
		}
		return -1;
	}
	
	public void add(Integer i)
	{
		a[size] = i;
		incrementSize();
	}
	
	
	public void heapify(int i)
	{
		if (i >= size)
			return; 
		
		int l = left(i);
		int r = right(i);
		
		int largest=i;
		if (l < size && a[l] > a[i])
		{
			largest=l;
		}
		
		
		if (r < size && a[r] > a[largest])
		{
			largest = r;
		}
		
		if (largest != i)
		{
			exchange(a, i, largest);
			heapify(largest);
		}
		
	}

	private static void exchange(Integer[] a, int i, int largest) {
		int tmp = a[i];
		a[i]=a[largest];
		a[largest]=tmp;
	}
	
	public void create(Integer n[])
	{
		for (int i = 0; i < n.length; ++i)
		{
			add(n[i]);
		}
		System.out.println(Arrays.deepToString(a));
		for(int i = size/2; i >= 0 ; --i)
		{
			heapify(i);
		}
		System.out.println(Arrays.deepToString(a));
		System.out.println("Removing max: "+min());
		System.out.println(Arrays.deepToString(a));
		
	}
	
	
	public static void main(String args[])
	{
		Integer a[] = {12, 4 , 5 , 7 , 8, 9, 13, 1 , 11};
		Heap heap = new Heap();
		heap.create(a);
	}
}
